package org.example.recursion;

/**
 * @author carol
 */
public class InsertSort {

    public static void insertSort(int[] arr){
        sort(arr, 1);
    }

    private static void sort(int[] arr,int index){
        // 右边区域为未排序区域，右边区域的最左侧是下一个排序的元素下标
        int current = index;
        if (current== arr.length){
            return;
        }
        int temp = arr[current];
        while (current>0){
            if(arr[current-1]>temp){
                arr[current] = arr[current-1];
                current--;
            }else {
                break;
            }
        }
        // 退出循环意味着已经找到了插入位置
        arr[current] = temp;
        sort(arr,index+1);
    }

    public static void main(String[] args) {

        int[] arr = {100,87,123,43,12,12,12,12,12,56,32,1,53,6,21,0,12};
        insertSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
